class Solution  {
public:
    vector<string> addOperators(string num, int target) {
        int n = num.size();
        vector<string> res;
        string str;

        function<void(int, int64_t, int64_t)> dfs = [&] (int index, int64_t sum, int64_t rear) {
            if (index == n && sum == target)
            {
                res.push_back(str);
                return;
            }
            
            int64_t x = 0, len = str.size();
            if (index) str.push_back('+'); 

            for(int i = index; i < n; ++i)
            {
                x = x * 10 + num[i] - '0';
                str.push_back(num[i]);
                if (index == 0) dfs(i + 1, x, x);
                else
                {
                    str[len] = '+';
                    dfs(i + 1, sum + x, x);      

                    str[len] = '-';
                    dfs(i + 1, sum - x, -x);

                    str[len] = '*';
                    dfs(i + 1, sum - rear + rear * x, rear * x);
                }
                if (x == 0)
                    break;
            }
            str.resize(len);
        };

        dfs(0, 0, 0);
        return res;
    }
};